#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
typedef struct TreeNode{
	int val;
	struct TreeNode* lchild, * rchild;
}TreeNode;
typedef struct Tree {
	TreeNode* root;
	int n;
}Tree;
TreeNode* NewNode(int val) {
	TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));
	assert(newnode);
	newnode->val = val;
	newnode->lchild = newnode->rchild = NULL;
	return newnode;
}
Tree* newtree() {
	Tree* newtree = (Tree*)malloc(sizeof(Tree));
	assert(newtree);
	newtree->n = 0;
	newtree->root = NULL;
	return newtree;
}
TreeNode* InsertNode(TreeNode* root,int val,int*ret) {
	if (root == NULL) {
		*ret = 1;
		return NewNode(val);
	}
	if (root->val == val) return root;
	if (root->val > val)root->lchild = InsertNode(root->lchild,val,ret);
	else root->rchild = InsertNode(root->rchild, val,ret);
	return root;
}
void insert(Tree* tree, int val) {
	int flag = 0;
	tree->root = InsertNode(tree->root, val,&flag);
	tree->n += flag;
	return;
}
void outputTreeNode(TreeNode* root) {
	if (root == NULL)return;
	printf("%d", root->val);
	if (root->lchild == NULL && root->rchild == NULL)return;
	printf("(");
	outputTreeNode(root->lchild);
	printf(",");
	outputTreeNode(root->rchild);
	printf(")");
	return;
}
void outputTree(Tree*tree) {
	printf("tree(%d)=", tree->n);
	outputTreeNode(tree->root);
	printf("\n");
	return;
}
void ClearTreeNode(TreeNode* tree) {
	if (tree == NULL)return;
	ClearTreeNode(tree->lchild);
	ClearTreeNode(tree->rchild);
	free(tree);
	return;
}
void ClearTree(Tree* tree) {
	if (tree == NULL)return;
	ClearTreeNode(tree->root); 
	free(tree);
	return;
}
void preorderNode(TreeNode* node) {
	if (node == NULL)return;
	printf(" %d", node->val);
	preorderNode(node->lchild);
	preorderNode(node->rchild);
	return;
}
void preorder(Tree* tree) {
	printf("preorder:");
	preorderNode(tree->root);
	printf("\n");
}
void inorderNode(TreeNode* node) {
	if (node == NULL)return;
	inorderNode(node->lchild);
	printf(" %d", node->val);
	inorderNode(node->rchild);
	return;
}
void inorder(Tree* tree) {
	printf("inorder:");
	inorderNode(tree->root);
	printf("\n");
}
void postorderNode(TreeNode* node) {
	if (node == NULL)return;
	postorderNode(node->lchild);
	postorderNode(node->rchild);
    printf(" %d", node->val);
	return;
}
void postorder(Tree* tree) {
	printf("preorder:");
	postorderNode(tree->root);
	printf("\n");
}
#define OPTION 10
int main() {
	srand((unsigned int)time(NULL));
	int n = OPTION;
	Tree* tree = newtree();
	for (int i = 0; i < n; i++) {
		int val = rand() % 100;
		insert(tree, val);
		outputTree(tree);
	}
	preorder(tree);
	inorder(tree);
	postorder(tree);
	ClearTree(tree);
	return 0;
}